package com.gitee.ywj1352.leecode;

/**
 * 堆排序
 *
 * @author wenjie.yang on 2019/9/11.
 */
public class HeapSort {
    //总数量
    private int[] arr;
    //堆容量
    private int n;
    //现存的数量
    private int c;

    // i-右-2i  i-左-2i+1
    //堆的数组 一个元素 为 0 不做 考虑
    public HeapSort(int n) {
        this.arr = new int[n + 1];
        this.n = n;
        c = 0;
    }

    //不停的 和他的 右子节点 交换
    public void insert(int a) {
        int idx = c + 1;
        arr[idx] = a;
        c++;
        int i = (idx) / 2;
        while (arr[i] < a && i > 0) {
            swap(i, idx, arr);
            idx = i;
            i = i / 2;
        }
    }

//    public int removeMax(){
//        int ri = arr[1];
//        //交换
//        swap(1,c--,arr);
//        arr[c+1] = 0;
//        int a = arr[1];
//        int i = 2;
//        int idx = 1;
//        while(arr[i]>a && i< n/2 +1){
//            swap(i, idx, arr);
//            idx = i;
//            i = i * 2;
//        }
//        return ri;
//    }


    //割补法  进行 堆化
    public int removeMax() {
        int max = arr[1];
        arr[1] = arr[c];
        arr[c] = 0;
        c--;
        int i = 1;
        while (arr[i] < arr[2 * i] && i < c) {
            swap(i, 2 * i, arr);
            i = i * 2;
        }
        return max;
    }

    private void swap(int i, int j, int[] arr) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort(8);
        heapSort.insert(2);
        heapSort.insert(3);
        heapSort.insert(29);
        heapSort.insert(104);
        heapSort.insert(9);
        heapSort.insert(1);
        heapSort.insert(49);
        heapSort.insert(39);
        System.out.println(heapSort);
        for (int i = 0; i < 8; i++) {
            System.out.println(heapSort.removeMax());
        }
    }


}
